Communication devices such as but not limited to routers and switches manage multiple flows of data. These data flows include multiple data packets that include data payloads as well as control information (also referred to as routing information) fields. The control information fields can be located in the header of the data packets but this is not necessarily so. The format of the control information depends upon the protocol stack that is being used by the communication device. In many cases the control information is included within first 160 bytes of a packet holding information of Layer two to Layer seven (referring to the OSI model).
A communication device, including a layer two or higher switch or other communication device, receives a data packet, extracts control information, processes the control information in order to decide how to process the data packet and eventually processes the data packet. The processing of the control information can include a classification stage and a forwarding stage. While classification involves applying flow control rules or policing, and forwarding may determine the queue that will receive the data packet as well as determining the output port of the communication device through with the data packet is to be sent.
The processing of the data packet can include terminating the data packet, forwarding the data packet to an output port of the communication device, performing error correction operations, converting the format of the data packet and the like.
Some of the communication devices are required to operate at wire-speed. Even communication devices that operate at sub-wire speed have to operate relatively quickly. In addition, these communication devices are required to be cost effective and to manage data packets that may includes relatively large control information fields.
For example, a typical communication switch can be required to process data packets that include layer two and even layer 3, 4, and/or 7 control information fields that can be up to sixty-four bits long. Future communication protocols may require even longer control information fields. Typical control information fields include source address, destination address, and the like.
Typically, one or more control information fields is used to form a key, the key is used to access a first data structure that usually includes a pointer to another data structure that in turn includes information that defines how to process the data packet.
One prior art device stored the first data structure in a content addressable memory (CAM). This solution is very costly, especially when the CAM stores the complete key and when the CAM is used to store a very large number of keys. Yet another solution involves storing the first data structure in an off-chip static random access memory (SRAM) unit. SRAM are very fast but are also expensive. Yet another solution involves storing the first data structure in an on-chip memory unit while consuming expensive VLSI area.
Yet another prior art solution involved applying a hash function on the key to provide a hashed value. The hashed value is used to access the first memory data structure efficiently. The hash function maps a very large virtual memory space spanned by the key to a much smaller memory space. This mapping can result in a collision—multiple different keys that are have the same hashed value. Collisions can be solved by allocating a set of memory entries for each hashed value. This solution is also referred to as chaining. Each memory entry of the set stores a key. When a new key is mapped to a hashed value the set of memory entries is scanned in order to find a vacant memory entry. Once such a vacant entry is found the key is stored in it.
Yet another solution for the collision problem involves allocating the next vacant memory entry to a colliding key. Yet a further solution involves using a second hash table for the colliding keys.
U.S. Pat. No. 5,339,398 of Shah et al., titled “Memory architecture and method of data organization optimized for hashing”, which is incorporated herein by reference, describes the chaining solution as well as a dual memory structure in which a first memory serves as a hash index table, for storing pointers at each address location corresponding to a hash value generated by hashing a key data word. Each pointer is the address of a location in a second memory, which has a separate storage location for each key data word, its associated data, and a further pointer which is the address of the next key data word resulting from a collision during hashing.
U.S. patent application 2003/0210689 of Davis et al., titled “Lookups by collision-less direct tables and CAMs”, which is incorporated herein by reference, describes a structure and technique for preventing collisions using a hash table in conjunction with a CAM to identify and prevent a collisions of binary keys. A portion of the hash value of a binary key, which does not collide with a portion of the hash value of any other reference binary key, is used as an entry in the hash table. If two or more binary keys have identical values of the portions of the hash values, each of these binary keys are stored in their entirety, in the CAM. The key in the CAM provides a pointer to a data structure where the action associated with that binary key is stored. If the binary key is not found in the CAM, the binary key is hashed, and a specific entry in the hash table is selected using a portion of this hash value.
U.S. patent application 2005/0114547 of Wu et al., titled “Network address and port number translation system” which is incorporated herein by reference, describes a network address and port number translation (NAPT) system which applies hashing to search data and uses a data store pool to resolve collision on searching. In addition, a list header and the data store pool form a list of free public port numbers, such that a first available free (not used) public port number can be taken from the list header while a new connection is set up.
U.S. Pat. No. 6,950,434 of Viswanath et al., titled “Arrangement for searching packet policies using multi-key hash searches in a network switch” which is incorporated herein by reference, describes a network switch, configured for performing layer 2 and layer 3 switching in an Ethernet network without blocking of incoming data packets. The network switch includes network switch ports, each including a flow module configured for generating a packet signature based on layer 3 information within a received data packet. The flow module generates first and second hash keys according to a prescribed hashing function upon obtaining first and second portions of layer 3 information. The flow module combines the first and second hash keys to form the packet signature, and searches an on-chip signature table that indexes addresses of layer 3 switching entries by entry signatures, where the entry signatures are generated using the same prescribed hashing function on the first and second layer 3 portions of the layer 3 switching entries.
U.S. Pat. No. 6,925,085 of Krishna et al. titled “Packet classification using hash key signatures generated from interrupted hash function” which is incorporated herein by reference describes a network switch, configured for performing layer 2 and layer 3 switching in an Ethernet network without blocking of incoming data packets. The network switch includes network switch ports, each including a packet classifier module configured for generating a packet signature based on information within a received data packet and hash action values specified within a user-programmable template. In particular, the network switch stores a plurality of user-programmable templates, each configured for identifying a corresponding class of data packet. Each user-programmable template includes hash action values specifying initiation and termination of a hash function based on a byte offset of a received data packet. The packet classifier module includes a hash generator configured for generating hash values for selected bytes of the received data packet, and a template translator configured for controlling the hash generator for hashing the selected bytes of the received data packet based on the hash action values specified by a corresponding user-programmable template. A unique hash signature can be generated by supplying a data frame having a prescribed data values at the selected bytes of the user-programmable template. The hash signature can then be stored for comparison with incoming data packets during network switching operations. Hence, data packets can be classified at the wire rate by performing a hash-based search of selected bytes of the received data packet.
U.S. Pat. No. 6,889,225 of Cheng et al., titled “Large database search using content addressable memory and hash”, which is incorporated herein by reference describes a hash-CAM (H-CAM) which may work with a controller and a memory containing a database of either search values and associate content or associate content by itself. The H-CAM includes at least one set of paired hash units and CAM units and at least one logic unit. The CAM units hold values known to cause hash collisions in the respectively paired hash units, and the logic unit prioritizes the hash and CAM unit outputs to a single address value usable to access the memory and obtain a search result at the controller that is not the result of a hash collision. The H-CAM may optionally include a search data storage to store the search values, so that they need not be stored in the memory, and a comparator to determine and handle newly determined hash collisions.
Additional hashing mechanism are illustrated in the following articles, all being incorporated herein by reference: “Balanced allocation”, Yossi Azar, Andrei Z. Broder, Anna R. Karlin, Eli Upfal, Proceedings of 26th STOC (1994), 593-602; “Expected length of the longest probe sequence in hash code searching”, G. H. Gonnet, J. Assoc. Comput. Mach., 28 (1981):289-304; and “How Asymmetry Helps Load Balancing”, B. Vöcking, Proc. 40th FOCS (New York, 1999), pp. 131-140.
There is a growing need to provide efficient devices and method for processing data packets.